Итерационные методы решения систем линейных уравнений

Метод итераций является численным методом для решения систем линейных уравнений. Эти системы могут быть записаны в виде:
Ax=b
где:
• A — квадратная матрица коэффициентов системы размерности n×n,
• x=(x1,x2,…,xn)T — вектор неизвестных, который необходимо найти,
• b=(b1,b2,…,bn)T — вектор правых частей.
Цель метода итераций — получить приближенное решение для вектора x путём последовательных вычислений. Каждый шаг метода предполагает улучшение приближения к решению, начиная с произвольного начального приближения.[1]
Метод итераций заключается в следующем процессе:
1. Преобразование системы уравнений. Для каждого уравнения системы выразить одну переменную через остальные.
2. Инициализация начального приближения: Выбирается начальный вектор x(0), который может быть произвольным (например, нулевым вектором).
3. Итерации. На каждом шаге вычисляется новое приближение x(k+1) из старого x(k) с использованием итерационной схемы.
4. Проверка сходимости: Процесс повторяется до тех пор, пока разница между двумя последовательными приближениями не станет достаточно малой, что означает, что решение сошлось.
Каждое уравнение из системы линейных уравнений можно записать так, чтобы одна из переменных выражалась через остальные. Для системы:
Ax=b
Cоставим итерационную схему. Пусть система имеет вид:
[a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2⋮an1x1+an2x2+⋯+annxn]
Теперь выразим x1,x2,…,xn1, xn2, через остальные переменные:
x1=b1−(a12x2+⋯+a1nxn)a11x1
Каждое из этих выражений и будет составлять отдельное уравнение в итерационной схеме. Это позволяет итерационно обновлять значения переменных в каждом шаге.
1.1 Начальное приближение и итерации
1.1.1 Выбор начального приближения
Для того чтобы начать процесс итераций, необходимо задать начальное приближение. Чаще всего начальное приближение выбирается как вектор нулевых значений:
x(0)=(0,0,…,0)T
Однако в некоторых случаях можно выбрать более обоснованное начальное приближение, если есть информация о возможных значениях переменных. Важно, чтобы начальное приближение не было слишком далеким от истинного решения, поскольку это может увеличить количество итераций.
После инициализации начального приближения, приступаем к вычислениям. На каждом шаге k вычисляются новые значения переменных по итерационной формуле:
xi(k+1)=(bi−∑j≠iaijxj(k))/aii для каждогоi=1,2,…,nx_i
Каждое новое значение переменной xi зависит от значений других переменных, вычисленных на предыдущем шаге.
Этот процесс повторяется, пока разница между x(k+1) не станет достаточно малой, что будет означать, что решение сошлось.
1.2 Разновидности метода итераций
1.2.1 Метод Якоби
Метод Якоби является простейшим вариантом метода итераций. В этом методе для каждого i-го уравнения вычисление новой переменной xi(k+1) производится только с использованием старых значений переменных x(k), полученных на предыдущем шаге.[2]
xi(k+1)=(bi−∑j≠iaijxj(k))/aii для каждогоi=1,2,…,nx_
Это означает, что на каждом шаге все переменные обновляются одновременно, и новые значения зависят от старых.
1.3 Условия сходимости
Для того чтобы метод итераций сходился, необходимо выполнить некоторые условия. Сходимость метода зависит от свойств матрицы AA, которая определяет систему линейных уравнений.
1.3.1 Условие диагонального преобладания
Одним из условий сходимости метода является диагональное преобладание. Это условие означает, что для каждого уравнения из системы выполняется неравенство:
∣aii∣>∑j≠i∣aij∣|
где aii — диагональный элемент, а aij — элементы, расположенные вне диагонали. Это условие гарантирует, что метод итераций будет сходиться.
Если матрица A симметрична и положительно определена, то метод итераций всегда сходится. Это условие также важно для многих алгоритмов, таких как метод сопряженных градиентов, который является улучшением метода итераций.
Метод итераций будет сходиться, если спектральный радиус матрицы итерационного оператора (матрицы, связанной с системой уравнений) меньше 1. Спектральный радиус — это наибольшее по модулю собственное значение этой матрицы.
1.4 Оценка сходимости метода итераций
Сходимость метода итераций зависит от матрицы A, определяющей систему уравнений. Рассмотрим подробнее, как можно оценить сходимость этого метода.
Количество итераций, необходимое для достижения требуемой точности, зависит от начального приближения и спектральных свойств матрицы. Число итераций можно оценить с помощью константы сходимости.
Метод итераций сойдется быстрее, если матрица A обладает следующими свойствами:
• Диагональное преобладание. Если для всех уравнений выполняется условие диагонального преобладания, то метод будет сходиться достаточно быстро.
• Хорошая обусловленность. Если система линейных уравнений хорошо обусловлена, то итерации сойдутся быстрее.
В противном случае, если система плохо обусловлена (например, если матрица A близка к сингулярной или имеет малые собственные значения), то сходимость может быть значительно замедлена.
Для оценки сходимости метода также полезно вычислить спектральный радиус итерационного оператора G, который является матрицей, полученной при преобразовании исходной системы в итерационную форму. Спектральный радиус определяется как максимальное по модулю собственное значение матрицы GG:
ρ(G)=max∣λi(G)∣
где λi(G) — собственные значения матрицы G. Если ρ(G)<1, то метод сходится. Если ρ(G)≥1, то метод не будет сходиться.
Метод итераций имеет ряд преимуществ и недостатков, которые следует учитывать при его применении в зависимости от конкретной задачи.
Преимущества:
• Простота реализации. Метод итераций легко реализовать на практике, так как его алгоритм не требует сложных вычислений.
• Низкие требования к памяти. Метод итераций использует только вектор текущих значений переменных, что требует минимальных вычислительных ресурсов.
• Подходит для разреженных систем. Если матрица A разреженная (содержит много нулевых элементов), то метод итераций может быть очень эффективен, так как при вычислениях используются только ненулевые элементы.
• Гибкость. Метод итераций может быть адаптирован для различных типов задач, включая те, где системы имеют особые структуры (например, диагональное преобладание или симметричные матрицы).
Недостатки:
• Не всегда сходится. Метод может не сходиться для систем с определёнными свойствами, такими как плохая обусловленность матрицы AA.
• Медленная сходимость. Для некоторых задач метод итераций может сходиться очень медленно, особенно если спектральный радиус итерационного оператора близок к 1 или система плохо обусловлена.
• Не даёт точного решения. Метод итераций является приближённым и не всегда может гарантировать получение точного решения в ограниченное число итераций. Точность зависит от количества итераций и выбора начального приближения.[3]